#include<bits/stdc++.h>
using namespace std;

typedef struct Linknode
{
    int data;
    struct Linknode* next;
}Linknode;

Linknode* Init()
{
    Linknode* L = (Linknode*)malloc(sizeof(Linknode));
    L->data = 0;
    L->next = NULL;
    return L;
}

void headinsert(Linknode* L,int data)
{
    Linknode* node = (Linknode*)malloc(sizeof(Linknode));
    node->data = data;
    node->next = L->next;
    L->next = node;
}

void print(Linknode* L)
{
    Linknode* node = (Linknode*)malloc(sizeof(Linknode));
    node = L->next;
    while(node)
    {
        printf("node=%d-->",node->data);
        node = node->next;
    }
    printf("NULL\n");
}

void tailinsert(Linknode* L,int data)
{
    Linknode* node = (Linknode*)malloc(sizeof(Linknode));
    Linknode* temp = (Linknode*)malloc(sizeof(Linknode));
    node = L;
    while(L->next)
    {
        L = L->next;
        node = node->next;
    }
    temp->data = data;
    temp->next = NULL;
    node->next = temp;
}

int L_len(Linknode* L)//求链表长度
{
    L = L->next;
    int i = 0;
    while(L)
    {
        i++;
        L = L->next;
    }
    return i;
}

void findNode(Linknode* L,int k)
{
    L = L->next;
    int i = 1;
    int j = L_len(L);
    while(L)
        if(k>j)
        {
            printf("NULL\n");
            break;
        }
        else
        {
            if(k==i)
            {
                printf("%d\n",L->data);
                break;
            }
            else if(i<k)
            {
                L = L->next;
                i++;
            }
    }
}

void print_midNumber(Linknode* L)
{
    int i = 1;
    int j = L_len(L);//将长度输入
    int number = j/2;
    L = L->next;
    if(j%2==1)//如果为奇数,因为是int类型÷ 值肯定是向下取整 所以while要多遍历一次例如1 2 3 3/2=1 但是中间值是第二个
    //所以i<=number
    {
        while(i<=number)
        {
            L=L->next;
            i++;
        }
        printf("中间值为:%d\n",L->data);
    }
     else if(j%2==0)//偶数就不需要多循环一次
     {
        while(i<number)
        {
            L = L->next;
            i++;
        }
        double a = L->data;//切记一定要是浮点类型 如果是int类型可能会出现精度丢失
        L = L->next;
        double b = L->data;
        printf("中间值:%lf",(a+b)/2);
    }

}

void find_same(Linknode* L,Linknode* J,int i,int j)//思路：通过两个链表合并得出的想法
//如果两个相等,就输出,如果不相等就把较小的那个节点向后移一个节点
{
    L = L->next;
    J = J->next;
    int m = 0;
    int n = 0;
    while(n<i&&m<j)
    {
        if(L->data==J->data)
        {
            printf("node=%d-->",L->data);
            L = L->next;
            J = J->next;
            i++;
            j++;
        }
        else if(L->data<J->data)
        {
            L = L->next;
            i++;
        }
        else if(J->data<L->data)
        {
            J = J->next;
            j++;
        }

    }
}

int main()
{
    Linknode* L=Init();
    tailinsert(L,1);
    tailinsert(L,2);
    tailinsert(L,3);
    tailinsert(L,4);
    Linknode* J=Init();
    tailinsert(J,1);
    tailinsert(J,3);
    tailinsert(J,4);
    tailinsert(J,5);
    int j = L_len(J);
    int i = L_len(L);;
    find_same(L,J,i,j);
    // print(L);
    // print(J);
}
